package 中等.模拟;

/**
 * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
 * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
 * P   A   H   N
 * A P L S I I G
 * Y   I   R
 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
 * 请你实现这个将字符串进行指定行数变换的函数：
 * string convert(string s, int numRows);
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zigzag-conversion
 */
public class Z字形变换_6 {

    public static void main(String[] args) {

        System.out.println(convert2("abcd", 2));

    }

    /**
     * 模拟
     * 假设
     * 1
     * 1  1
     * 1
     * 为一个周期
     * 已知：长度为n，行数为r
     * 那么一个周期的字符串长度为
     * 2r-2
     * 占用的列为
     * 1+r-2=r-1
     * <p>
     * 二维数组总共需要的最少列为
     * n/(2r-2)周期个数*(r-1)一个周期的列+t
     *
     * @param s
     * @param numRows
     * @return
     */
    public static String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        StringBuilder stringBuilder = new StringBuilder();
        int n = s.length();
        int t = 2 * numRows - 2;
        int columns = (n / t + 1) * (numRows - 1);  //可能除不尽，多加一个周期
        char[][] temp = new char[numRows][columns];
        //一列一列赋值
        //往下走row+1，column不变，向上，row-1，column+1！！！
        boolean flag = true;  //true为向下走
        for (int row = 0, column = 0, sIndex = 0; sIndex < s.length(); sIndex++) {
            if (flag) {  //向下
                temp[row][column] = s.charAt(sIndex);
                row++;
                if (row == numRows) {  //超出一行
                    flag = false;
                    row -= 2;
                    column++;
                    if (row == 0) {  //rows=2时，会到达下一个周期起点
                        flag = true;
                    }
                }
            } else {  //向上
                temp[row][column] = s.charAt(sIndex);
                row--;
                column++;
                if (row == 0) {
                    flag = true;
                }
            }
        }
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < columns; j++) {
                if (temp[i][j] != 0) {
                    stringBuilder.append(temp[i][j]);
                }
            }
        }
        return stringBuilder.toString();
    }


    /**
     * 使用stringbuilder[]数组来模拟，可以减少一些空字符空间
     *
     * @param s
     * @param numRows
     * @return
     */
    public static String convert2(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        StringBuilder[] stringBuilders = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {  //需要自己创建默认对象
            stringBuilders[i] = new StringBuilder();
        }
        //往下走row+1，向上，row-1，此时无需关注列
        boolean flag = true;  //true为向下走
        for (int row = 0, sIndex = 0; sIndex < s.length(); sIndex++) {
            if (flag) {  //向下
                stringBuilders[row].append(s.charAt(sIndex));
                row++;
                if (row == numRows) {  //超出一行
                    flag = false;
                    row -= 2;
                    if (row == 0) {  //rows=2时，会到达下一个周期起点
                        flag = true;
                    }
                }
            } else {  //向上
                stringBuilders[row].append(s.charAt(sIndex));
                row--;
                if (row == 0) {
                    flag = true;
                }
            }
        }
        for (int i = 1; i < numRows; i++) {
            stringBuilders[0].append(stringBuilders[i]);
        }
        return stringBuilders[0].toString();
    }

}
